package difficult;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution_1235 {
    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime.length == 0) {
            return 0;
        }

        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < endTime.length; i++) {
            List<Integer> list = map.getOrDefault(endTime[i], new ArrayList<>());
            list.add(i);
            map.put(endTime[i], list);
        }

        int[] ends = Arrays.copyOf(endTime, endTime.length);
        Arrays.sort(ends);
        int[] flag = new int[ends[ends.length-1]-ends[0]];

        int value = 0, sameIndex = 0;
        Set<Integer> set = new HashSet<>();
        List<Integer> endTimeList = new ArrayList<>();
        List<Integer> valueList = new ArrayList<>();
        for (int i = 0; i < ends.length; i++) {
            if (i>0) {
                for (int k = ends[i-1]; k < ends[i]; k++) {
                    flag[k-ends[0]] = endTimeList.size()-1;
                }
            }
            List<Integer> list = map.get(ends[i]);
            Integer index = list.get(sameIndex++);
            if (sameIndex == list.size()) {
                sameIndex = 0;
            }
            if (valueList.isEmpty()) {
                value = profit[index];
            } else {
                int maxValue = valueList.get(valueList.size() - 1);
                int compareVal = profit[index];

                int m = startTime[index]-ends[0];
                int tempIndex = m<0?-1:flag[m];
                compareVal += tempIndex == -1 ? 0 : valueList.get(tempIndex);
                maxValue = Math.max(maxValue, compareVal);
                value = maxValue;
            }
            Integer oldValue;
            if (!set.contains(ends[i])) {
                endTimeList.add(ends[i]);// 保存结束时间点
                valueList.add(value);
                set.add(ends[i]);
            } else {
                oldValue = valueList.get(valueList.size()-1);
                value = Math.max(oldValue, value);
                valueList.set(valueList.size()-1, value);
            }
            // System.out.println("time:" + endTime[i] + ",profit:" + value);
        }
        return value;
    }

    public static void main(String[] args) {
//        System.out.println(jobScheduling(new int[]{1,1,1}, new int[]{2,3,4}, new int[]{5,6,4}));
//        System.out.println(jobScheduling(new int[]{1}, new int[]{1}, new int[]{50}));
//        System.out.println(jobScheduling(new int[]{1,2,3,3}, new int[]{3,4,5,6}, new int[]{50,10,40,70}));
        /*System.out.println(jobScheduling(new int[]{186,107,96,311,433,160,478,441,112,46,1097,964,1187,1233,1214,1156,1141,916,916,1175,1848,1926,1964,1852,2026,1918,2079,1870,1634,1640,2597,2700,2644,2628,2793,2895,2513,2770,2719,2657,3378,3407,3239,3445,3537,3378,3539,3260,3582,3505,4302,4331,4036,4102,4007,4299,4122,4380,4339,4159,5113,4856,4973,5227,4951,4847,4987,5002,4896,5021,5955,5743,5992,5952,5660,6072,5640,6031,5610,5758,6770,6556,6765,6476,6522,6588,6556,6568,6835,6676,7500,7479,7202,7473,7476,7517,7656,7596,7261,7566,8432,8023,8180,8177,8310,8474,8117,8447,8020,8138,9204,9233,8952,9256,9097,9142,9170,9186,9016,9071,9808,9734,9696,9982,9842,9978,9651,9866,9865,9948,10765,10735,10413,10813,10848,10662,10625,10524,10562,10780,11575,11552,11663,11394,11518,11345,11226,11432,11324,11582,12411,12161,12014,12281,12116,12252,12191,12197,12462,12098,12923,12919,12866,13110,13151,13107,13291,12940,13224,13065,14005,13628,13910,13673,13980,13906,13806,13957,14020,13845,14793,14894,14649,14433,14765,14890,14464,14708,14581,14648,15555,15550,15368,15450,15533,15478,15278,15520,15475,15484,16370,16449,16248,16017,16408,16029,16275,16315,16371,16187,17170,17080,16835,17077,17272,17062,17146,17152,16881,16806,18056,17916,17926,17638,17889,18058,17811,17916,17675,18062,18657,18432,18798,18739,18842,18556,18416,18768,18602,18899,19385,19682,19233,19423,19365,19327,19471,19675,19558,19421,20365,20291,20332,20413,20183,20459,20027,20393,20443,20255,21145,20922,21101,21037,20904,20836,21269,20929,20821,21084,21749,21870,21902,21688,21832,21932,21733,21937,21866,21881,22566,22818,22536,22802,22548,22647,22730,22889,22740,22435,23604,23299,23448,23350,23518,23300,23321,23595,23685,23364,24072,24399,24101,24477,24452,24071,24125,24211,24455,24437,24835,25288,25251,25212,25109,24958,25046,25162,24837,24895,26041,25717,26032,26014,25899,25862,25746,25770,25769,26032,26609,26447,26486,26683,26624,26659,26599,26521,26721,26703,27316,27667,27475,27292,27478,27557,27400,27363,27579,27569,28441,28438,28047,28480,28096,28044,28240,28364,28297,28263,28996,29082,28940,28859,29084,28931,28818,28917,28891,29077,29933,29635,30031,30096,29931,30008,29656,29950,29965,29848,30576,30770,30477,30483,30568,30755,30517,30484,30443,30618,31286,31610,31621,31301,31606,31680,31327,31501,31680,31254,32426,32387,32126,32482,32045,32131,32046,32296,32497,32400,33210,32811,32846,33053,33024,33177,33292,33040,32943,33288,33883,33842,33712,33630,33817,33902,33814,34019,33976,33900,34642,34704,34461,34716,34458,34506,34659,34662,34633,34437,35388,35271,35333,35309,35265,35629,35569,35590,35273,35574,36246,36434,36141,36378,36387,36143,36062,36184,36049,36406,37103,36981,36899,37018,37150,36948,37196,37041,36884,37014,37633,37956,38100,38086,37971,37887,37728,37788,37769,37972,38465,38565,38713,38405,38411,38870,38707,38841,38567,38780,39524,39645,39320,39462,39354,39552,39607,39270,39544,39398,40461,40080,40080,40027,40215,40467,40138,40389,40036,40382,40999,41218,40914,41084,41117,41085,40830,41109,40852,40858,41781,41811,42095,41840,42093,41798,41996,41883,41943,41810,42708,42869,42687,42690,42492,42897,42504,42894,42461,42859,43429,43388,43514,43594,43466,43678,43202,43535,43620,43570,44496,44232,44393,44093,44128,44285,44201,44060,44027,44039,45114,45250,45112,45217,45006,44885,44879,45007,45087,45160,46015,46053,45896,45771,45679,45765,45829,45891,45931,45683,46819,46482,46420,46481,46880,46511,46783,46637,46417,46743,47692,47404,47313,47474,47412,47511,47354,47382,47491,47666,48188,48198,48471,48252,48219,48335,48370,48333,48334,48431,48970,49011,49012,48906,48873,49095,48990,49202,48911,49218,49798,49893,49868,49755,50007,49765,49760,49607,49982,49761,50423,50828,50460,50660,50741,50444,50824,50651,50787,50474,51540,51652,51688,51319,51234,51532,51483,51330,51549,51346,52445,52459,52058,52186,52009,52156,52062,52405,52405,52174,52870,52956,52917,52951,53235,53113,52965,53175,53271,53120,53611,53760,53964,53963,53851,53911,53901,53991,53966,54024,54815,54609,54896,54608,54572,54596,54516,54520,54452,54875,55402,55458,55340,55557,55361,55455,55297,55204,55349,55526,56067,56103,56326,56441,56453,56391,56101,56008,56236,56433,57037,57030,57028,56957,57299,57068,56984,56834,57213,56966,58083,57818,58082,57950,57646,58077,58040,57666,57896,57692,58579,58420,58750,58716,58464,58850,58546,58523,58406,58487,59336,59321,59672,59272,59359,59483,59227,59203,59555,59622,60034,60493,60026,60128,60273,60117,60497,60416,60160,60373,60900,61168,60987,61299,60811,60841,60994,61100,61103,61221,61774,61779,61934,61684,62075,61658,61652,61716,61711,61669,62612,62890,62720,62664,62855,62554,62696,62658,62665,62418,63227,63692,63284,63410,63629,63455,63405,63440,63208,63658,64295,64028,64072,64090,64036,64245,64487,64384,64208,64307,64934,64858,65019,64978,65279,64896,64960,65202,64806,65204,65806,65944,65778,66062,65718,65816,65971,66066,65736,65860,66692,66582,66661,66873,66568,66565,66748,66441,66651,66409,67522,67543,67469,67376,67271,67630,67672,67434,67414,67600,68067,68194,68421,68432,68103,68039,68479,68268,68021,68018,69279,69001,68898,68943,69295,68925,69239,68936,69193,69229,69798,69647,70088,69735,69788,69857,69626,69973,70075,70064,70514,70743,70460,70432,70484,70410,70454,70628,70580,70558,71531,71289,71618,71546,71460,71488,71535,71326,71640,71455,72170,72020,72265,72043,72013,72170,72017,72398,72135,72031,73104,72931,73156,73154,72907,73286,73124,72874,73028,73090,73920,73707,73648,73679,73822,74084,74093,73608,73693,73633,74579,74618,74617,74497,74448,74702,74803,74637,74511,74443,75236,75618,75529,75407,75276,75669,75272,75657,75527,75367,76166,76318,76349,76204,76028,76173,76104,76297,76010,76202,76930,77086,77272,77296,76803,77066,77019,77182,76919,76835,77749,77961,77975,77676,78089,78047,77708,77766,78097,77831,78754,78669,78547,78469,78778,78606,78429,78475,78416,78440,79512,79423,79398,79459,79322,79340,79686,79467,79600,79409},
            new int[]{412,423,935,505,964,978,548,881,772,587,1454,1671,1543,1721,1686,1255,1596,1635,1743,1481,2006,1941,2111,2479,2293,2280,2110,2601,2302,1703,3048,3057,2825,3310,2798,2929,2647,2974,2759,2718,3462,3800,3993,3602,3885,3786,3783,3474,3802,3944,4816,4659,4463,4644,4008,4540,4596,4816,4459,4295,5246,5740,5626,5528,5643,5011,5071,5572,4956,5399,6479,6538,6118,6387,6587,6236,5988,6101,5656,6306,6845,7320,7284,6627,7351,7238,6563,7047,7111,7068,7757,8196,7220,7841,7892,8168,7897,8174,7340,7681,8956,8756,8366,8520,8728,8532,8556,8855,8907,8423,9350,9666,9012,9426,9396,9639,9512,9574,9049,9351,10589,10549,9923,10327,10286,10329,9769,9878,9918,10409,10981,10782,10761,11209,11321,10741,10731,10943,10959,11225,11640,12167,12064,12060,11525,12124,12030,11969,11990,12017,12531,12896,12509,12353,12448,12551,12706,12842,12552,12420,13320,13564,13043,13483,13167,13228,13303,13504,13291,13785,14463,13854,14551,14034,14022,14510,14225,14413,14373,13934,15174,15293,15387,14528,14792,15165,14483,15207,15201,14865,16035,15882,16115,15975,15788,16155,15642,15728,15781,16022,16992,16540,16330,16430,16745,16162,16870,16788,16790,16656,17355,17255,17264,17365,17372,17342,17436,17690,17395,16809,18389,18009,17960,18409,18586,18395,17937,18223,18407,18407,19136,18596,19399,19092,19079,18623,19273,19259,19396,19090,19521,19986,19925,19823,19839,19364,19952,20100,20002,19837,20963,20958,20479,20510,20304,20747,20273,20605,20816,20534,21505,21440,21526,21137,21468,20948,21349,21235,21418,21323,22250,21971,22418,21833,22111,22146,22433,22038,22177,22443,22879,23161,22882,23290,22676,23004,23392,23321,23177,22896,23911,23300,23745,24090,23807,23382,23991,23971,23855,23668,24187,24789,24492,24814,24734,24892,24842,24337,24939,24617,25499,25461,25561,25624,25364,25446,25055,25385,25722,25755,26229,25841,26144,26434,26199,26322,26185,26394,26070,26426,27206,26787,26834,26983,27110,27345,26927,26621,27121,26932,27408,28063,27545,27816,27787,28197,27937,27636,28149,28058,28924,28567,28661,28588,28259,28946,28605,28688,28713,28419,29563,29214,29431,29146,29171,29093,29369,29236,29708,29300,30341,30104,30421,30267,30074,30066,30278,30522,30301,30560,30938,31272,31314,31049,30861,31363,30854,30834,30938,30697,31651,31678,31873,31861,31750,31879,31870,31939,31848,31268,32653,32745,32548,32493,32680,32268,32678,32948,32982,32745,33725,32987,33378,33726,33767,33380,33638,33342,33582,33356,34370,34346,34246,33815,34484,34436,34201,34059,34258,33946,34706,34925,35114,35101,34517,34609,34974,34898,34781,34471,35910,35805,36159,35327,35990,36033,35871,35988,35630,35618,36387,36681,36675,36898,36416,36692,36480,36350,36918,36481,37606,37325,37089,37633,37332,37339,37350,37489,37309,37299,38229,38051,38252,38257,38256,38249,37769,38467,37855,38072,39263,38705,39401,38730,39269,39183,39367,39053,39200,39111,39572,39937,39408,40022,39839,39712,40027,39632,39701,39677,40592,40674,40927,40491,40514,40632,40200,40492,40731,40664,41029,41311,41531,41519,41709,41097,41442,41414,41487,40880,42458,42204,42191,41932,42375,42508,42066,42179,42079,42082,42998,43203,42852,43139,43305,43260,43320,43011,43178,43273,44088,44078,43906,44161,44196,44116,43851,43989,44190,43607,44860,44323,44704,44855,44966,44977,44310,44397,44649,44090,45171,45741,45724,45349,45191,45153,45266,45362,45297,45536,46466,46496,46389,46402,46427,45883,46446,46175,46093,45933,47384,46749,46563,47088,47213,47331,46808,46912,46610,46812,48086,47806,47859,47652,47757,48059,47611,47508,47966,47765,48219,48534,48857,48460,48296,48441,48939,48620,48995,48785,49021,49748,49419,49030,49118,49418,49549,49241,49436,49381,50393,50223,50304,50500,50078,50504,49816,50154,50105,50340,50550,51375,50537,51301,50962,51390,51391,51178,51126,50866,51712,52097,51765,51334,52108,51969,52067,51423,51743,51976,52922,52543,52071,52242,52015,52225,52172,52419,52522,52713,53510,53772,53659,53085,53331,53233,53531,53797,53658,53326,53639,54030,54128,54500,54399,54031,54571,54540,54144,54089,55298,54989,55249,54960,55227,55044,54713,54933,54968,54878,56011,55825,55459,55659,55407,55952,56074,55813,55919,56081,56218,56183,56474,56682,56856,56870,56733,56333,56970,56773,57559,57628,57126,57229,57448,57365,57554,57146,57618,57065,58272,58110,58574,58329,58080,58430,58514,58578,57923,57745,58754,58782,59258,59263,58843,59062,59204,59348,58441,58698,59727,60066,60191,60188,59612,59998,59842,60146,59832,59857,60186,60739,60368,60409,60418,60758,60771,60766,60614,60418,60961,61299,61448,61779,61364,61188,61770,61691,61661,61772,62525,62235,62310,62473,62117,62215,61653,62451,61773,62253,63191,62930,63317,62996,63276,62818,62746,62825,62691,62872,63964,63813,63406,63414,63918,63983,63908,64052,63210,63895,64954,64834,64401,64660,64170,64400,64935,64723,64809,64551,65474,65733,65736,65529,65356,65673,65304,65235,65742,65656,66244,66025,66319,66192,65872,66546,66174,66165,65776,66177,67348,67218,67362,67196,67203,66813,67021,66898,67078,67335,67871,68032,67873,67640,67920,67914,68060,67661,67546,68032,68215,68380,68473,68690,68334,68702,68760,68942,68763,68511,69677,69464,69800,69359,69393,69117,69761,69155,69750,69655,70329,70185,70530,69924,69940,70060,69654,70485,70335,70440,71170,71094,71276,71174,70759,70716,71138,71399,70807,70785,72113,71413,71875,72085,71547,72190,71766,71914,71670,72120,72278,72085,72483,72314,72341,72449,72289,72865,72818,72582,73751,73460,73686,73537,73059,73677,73448,73582,73653,73180,74104,73761,74314,74219,73951,74093,74555,74537,73778,74021,75219,75330,75382,74768,75235,74974,75058,75259,74704,74954,75240,75774,75578,75683,75772,76148,76143,75781,75625,75693,76242,76933,76525,76339,76589,76768,76985,76454,76262,76942,77041,77741,77525,77399,77393,77566,77124,77686,77531,77079,78221,78289,78536,78019,78401,78460,78351,77815,78512,78306,78883,79142,79106,78602,79065,79156,78566,78570,79068,78693,79760,80082,79738,79761,79380,79805,80012,79732,80065,79742},
            new int[]{652,523,379,710,747,255,256,353,544,572,469,355,639,349,289,572,651,404,189,604,773,489,986,672,496,105,318,571,982,446,886,542,233,913,48,536,329,469,267,820,668,887,413,182,532,649,726,639,256,630,603,829,888,800,447,675,506,174,370,964,813,765,84,817,693,40,360,209,726,583,374,621,739,114,772,423,570,606,271,881,493,536,513,76,402,117,987,151,122,222,254,339,241,994,553,796,281,368,827,539,469,217,162,718,478,997,690,559,537,272,134,811,778,929,306,401,933,562,708,453,561,594,62,976,343,179,233,687,648,813,203,803,862,135,151,35,119,373,393,996,192,559,437,760,671,365,394,981,404,829,204,738,48,147,238,85,914,404,87,921,581,348,87,55,531,138,570,466,107,914,915,929,935,320,891,473,569,199,542,155,983,54,553,516,711,746,504,986,289,137,585,608,711,458,194,58,948,1,36,427,952,481,542,868,236,95,430,543,676,998,335,366,943,770,775,257,530,834,684,318,340,70,615,650,684,792,722,242,261,686,32,291,428,228,603,893,28,822,385,817,110,722,802,586,905,497,713,767,813,742,101,253,279,638,267,696,551,588,780,620,549,552,354,257,702,272,811,715,315,148,22,196,404,725,976,695,658,653,10,973,775,477,256,643,93,29,518,125,596,862,796,219,773,635,210,594,168,401,601,905,613,48,550,891,782,577,863,495,404,395,836,311,192,762,381,25,252,512,97,398,898,47,108,893,722,881,375,211,628,673,121,266,174,583,103,85,250,213,465,242,874,285,573,107,616,860,370,508,107,350,615,232,825,419,488,766,873,798,530,387,260,622,325,840,165,909,155,301,203,360,614,422,171,239,463,652,902,717,263,379,804,868,256,488,353,928,432,266,59,525,580,147,529,142,827,389,279,718,904,816,474,892,464,981,720,724,828,981,530,410,85,719,106,959,492,362,701,773,611,980,771,875,584,784,998,736,932,37,914,150,719,501,11,403,918,371,87,659,649,594,144,872,251,96,912,29,498,855,887,313,815,419,568,361,508,863,939,424,872,187,685,500,151,272,626,928,746,891,783,306,395,912,933,602,728,318,348,923,26,517,123,170,603,649,233,950,41,630,105,21,475,431,681,358,684,53,115,446,54,809,193,928,673,727,126,614,134,476,411,117,512,526,229,839,800,137,391,449,521,56,637,672,712,55,478,316,701,156,226,601,736,972,924,994,627,916,810,915,311,455,183,814,679,753,528,967,423,291,559,930,574,97,576,339,65,270,907,988,672,752,355,385,377,280,129,551,332,319,612,473,384,331,590,819,620,557,104,621,836,52,434,149,778,952,448,31,40,660,201,486,680,983,16,489,933,626,646,766,28,789,528,343,931,610,421,843,175,701,575,136,474,554,196,787,931,179,489,618,902,494,719,251,73,390,667,995,516,624,532,11,916,331,691,824,938,704,82,731,82,854,913,106,182,567,921,948,867,548,891,157,979,419,803,84,565,706,931,103,401,123,271,65,631,353,592,63,402,141,98,856,947,601,392,577,948,287,695,837,986,235,689,822,957,254,295,137,694,573,475,184,183,807,749,505,196,385,988,452,685,254,843,613,812,990,75,860,65,176,754,720,581,492,709,853,327,899,714,217,430,697,402,280,83,740,455,59,184,304,429,396,230,808,898,425,797,125,705,864,153,512,734,116,95,409,766,15,825,144,331,946,713,271,752,240,157,771,333,257,49,423,575,975,93,423,675,9,19,859,219,77,589,69,681,171,457,829,56,202,674,467,367,512,855,530,815,68,678,692,844,314,51,545,886,830,686,913,648,114,551,896,431,238,317,751,158,185,350,437,323,169,523,58,959,942,887,709,140,933,983,71,571,472,146,904,631,840,989,791,899,727,57,514,326,875,370,951,562,336,620,295,694,416,599,274,845,491,686,704,63,748,780,812,736,936,613,697,481,270,86,477,740,320,421,204,386,458,639,886,512,155,467,152,315,742,598,718,517,764,66,971,378,881,134,246,732,188,222,22,788,404,325,539,671,181,395,336,698,184,274,720,453,589,827,865,395,647,985,91,746,295,632,136,865,349,86,413,625,156,772,309,583,800,571,815,124,268,769,497,322,153,125,342,609,180,162,854,448,21,533,105,607,305,838,38,924,529,558,352,344,113,401,219,260,519,810,825,886,435,889,548,801,326,631,958,664,56,976,932,908,545,328,996,56,194,547,414,171,868,510,743,590,779,286,905,986,252,676,422,75,479,330,772,167,452,842,628,974,611,387,177}));
    */
    }
}
